/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-07 12:51:22
 * @LastEditors: lily
 * @LastEditTime: 2021-04-07 14:59:06
 */
/*
 * @Descripttion:
 * @version:
 * @Author: lily
 * @Date: 2021-04-07 12:51:22
 * @LastEditors: lily
 * @LastEditTime: 2021-04-07 13:46:40
 */
/**
 * initialize your data structure here.
 */


import Heap from './heap'

var MedianFinder = function () {
    // 最大堆保存 小的那一半数字
    this.maxHeap = new Heap()
    // 最小堆保存 大的那一半数字
    this.minHeap = new Heap((x, y) => x < y)
};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function (num) {
    this.maxHeap.insert(num);  // 往最大堆插入元素
    this.minHeap.insert(this.maxHeap.top());  // 往最小堆插入最大堆堆顶
    this.maxHeap.extract(); // 去掉堆顶 重排最大堆
    if (this.maxHeap.container.length < this.minHeap.container.length) {
        this.maxHeap.insert(this.minHeap.top()); // 往最大堆里面插入最小堆堆顶
        this.minHeap.extract();// 去掉堆顶 重排最小堆
    }
};

/**
 * @return {number}
 */

//  思路：
//  1.暴力法：排序 
//    复杂度：O(nlogn) O(n)
//  2.二分查找：每次插入都保证数组是有序的 
//    复杂度：O(n) O(n)
//  3.最大堆+最小堆
//    复杂度：O(logn) O(n)

MedianFinder.prototype.findMedian = function () {
    return this.maxHeap.container.length > this.minHeap.container.length
        ? this.maxHeap.top()
        : (this.maxHeap.top() + this.minHeap.top()) / 2;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * var obj = new MedianFinder()
 * obj.addNum(num)
 * var param_2 = obj.findMedian()
 */
